import java.util.*;

/**
 * @author hewei
 * @version 1.0
 * @description: TODO
 * @date 2022/9/24 15:33
 */

public class BallGame {

    public static void main(String[] args) {
        String[] nums = {"W.W.WE..",".WWWEW..","EWW.WE.E","E.W.E.E.",".OEOO.EO","WE.WOE.W","WW...E..",".WEWO..O","E....E..",".OWE...."};
        System.out.println(Arrays.deepToString(new BallGame().ballGame(69, nums)));
    }

    public int[][] ballGame(int num, String[] plate) {
        List<Node> list = new ArrayList<>();
        int[][] desi = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        Deque<Node> queue = new LinkedList<>();
        char[][] chars = new char[plate.length][plate[0].length()];
        HashSet<Node> set = new HashSet<>();
        for (int i = 0; i < plate.length; i++) {
            for (int j = 0; j < plate[0].length(); j++) {
                chars[i][j] = plate[i].charAt(j);
                if (chars[i][j] == 'O') {
                    for (int k = 0; k < 4; k++) {
                        Node node = new Node(k, i, j);
                        if (!set.contains(node)) queue.add(node);
                        set.add(node);
                    }
                }
            }
        }
        while (!queue.isEmpty() && num-- > 0) {
            int size = queue.size();
            while (size-- > 0) {
                Node poll = queue.poll();
                int des = poll.des;
                int x = poll.x + desi[des][0];
                int y = poll.y + desi[des][1];
                if (x >= 0 && x < chars.length && y >= 0 && y < chars[0].length) {
                    if (chars[x][y] == 'W') {
                        des += 1;
                        if (des > 3) des = 0;
                    } else if (chars[x][y] == 'E') {
                        des -= 1;
                        if (des < 0) des = 3;
                    }
                    Node node = new Node(des, x, y);
                    if (set.contains(node)) continue;
                    if (x == 0 || y == 0 || x == chars.length - 1 || y == chars[0].length - 1) {
                        if (((x > 0 && x < chars.length - 1) || (y > 0 && y < chars[0].length - 1)) && chars[x][y] == '.') {
                            if ((x > 0 && x < chars.length - 1 && des != 0 && des != 2) || (y > 0 && y < chars[0].length - 1 && des != 3 && des != 1))
                            list.add(node);
                        }
                    }
                    queue.add(node);
                    set.add(node);
                }
            }
        }
        int[][] ans = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            Node node = list.get(i);
            ans[i][0] = node.x;
            ans[i][1] = node.y;
        }
        return ans;
    }

    public int process(int i) {
        if (i == 0) return 2;
        if (i == 1) return 3;
        if (i == 2) return 0;
        return 1;
    }

    static class Node {
        int des;
        int x;
        int y;

        public Node(int des, int x, int y) {
            this.des = des;
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "des=" + des +
                    ", x=" + x +
                    ", y=" + y +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return des == node.des && x == node.x && y == node.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(des, x, y);
        }
    }
}
